public class N {
    /*  public static int fac(int n){
          if(n == 1){
              return 1;
          }          //递归求 N 的阶乘
          return  n* fac(n -1);
      }


      public static void main(String[] args){
                 int ret = fac(3);
                 System.out.println(ret);
      }
  }*/
   /* 递归求 1 + 2 + 3 + ... + 10
public static int fun(int n){
    if(n == 1){
        return 1;
    }
    return n+fun(n-1);
}
    public static void main(String[] args){
        int ret = fun(10);
        System.out.println(ret);
  }
}*/
    /*按顺序打印一个数字的每一位(例如 1234 打印出 1 2 3 4)    （递归）
    public static void print(int n) {
        if (n < 10) {
            System.out.print(n+" ");
            return;
        }
        print(n / 10);
        System.out.print(n % 10+" ");


    }
    public static void main(String[] args) {
           int n = 1234;
           print(n);

    }
}*/
    /*写一个递归方法,输入一个非负整数,返回组成它的数字之和
    public static int sum(int n){
       if(n<10){
           return n;
       }
      return  n % 10 +sum(n/10);
    }
public static void main(String[] args) {
    int n = 1234;
    System.out.print(sum(n));
    }
}*/
    //递归求斐波那契数列的第 N 项
/*public static  int fib(int n){
    if(n == 1|| n== 2){
        return 1;
    }
    return fib(n - 1) + fib(n -2);
}
    public static void main(String[] args) {
               int ret = fib(1);
               int ret2 = fib(2);
               int ret3 = fib(5);
           System.out.println(ret);
           System.out.println(ret2);
           System.out.println(ret3);
    }
}*/
    //递归求解汉诺塔问题
    private static int count = 0;
    public static void move(char x,int n,char y){
        System.out.println("move"+" "+ n+" "+"from"+" " +x+" "+"to"+" "+y);
    }

    public static void hanio(int n,char x,char y,char z){
        count++;
        if(n == 1){
            move(x,n,z);
        }else {
            hanio(n - 1, x, z, y);
            move(x,n, z);
            hanio(n - 1, y, x, z);
        }
    }
    public static void main(String[] args) {
        hanio(3,'x','y','z');
        System.out.println(" 总共移动了 " + count + " 次" );
    }
}